#include"DynamicArray.h"
#include<iostream>
#include<cmath>


DynamicArray::DynamicArray():capacity(15),size(0)
{
   array=new ElementType[capacity];
   Free=nullptr;
}
DynamicArray::DynamicArray(const DynamicArray& a)
{
    size=a.size;
    capacity=a.capacity;
    array=new ElementType[capacity];
   for(size_t i=0;i<size;i++)
   {
    array[i]=a.array[i];
   }
}
 DynamicArray& DynamicArray:: operator=(const DynamicArray& a)
 {
        delete[]array;
         size=a.size;
        capacity=a.capacity;
        array=new ElementType[capacity];
    for(size_t i=0;i<size;i++)
    {
        array[i]=a.array[i];
    }

    return *this;

 }
 DynamicArray::~DynamicArray()
 {
        if(Free)
        {
            for(size_t i=0;i<size;i++)
            {
                Free(array[i]);//通过回调函数释放数组元素
            }
        }
        delete[]array;//释放数组
 }

 void DynamicArray::Inserttail(const ElementType &element)//不扩容O(1)扩容O(n)
 {
    if(size==capacity)//数组满
    {
        ReSize(capacity*2);
    }
    array[size++]=element;
    

 }

 void DynamicArray::InsertHead(const ElementType &element)//O(n)
 {
    if(size==capacity)//数组满
    {
        ReSize(capacity*2);
    }
    for(size_t i=size;i>0;i--)
    {
        array[i]=array[i-1];
    }
    array[0]=element;
    size++;

 }

 void DynamicArray::InsertByIndex(const ElementType &element, size_t index)
 {
    if(index>size)
    {
        std::cout<<"插入位置非法！\n";
        return;
    }
      if(size==capacity)//数组满
    {
        ReSize(capacity*2);
    }
     for(size_t i=size;i>index;i--)
    {
        array[i]=array[i-1];
    }
    array[index]=element;
    size++;
 }

 void DynamicArray::RemoveByindex(size_t index)//O(n)
 {
      if(index>=size)
    {
        std::cout<<"删除位置非法！\n";
        return;
    }
    for(size_t i=index;i<size-1;i++)
    {
        array[i]=array[i+1];
    }
    size--;

 }

 void DynamicArray::RemoveByelement(const ElementType &element)//O(n^2)
 {
    
    for(size_t i=0;i<size;i++)
    {
        if(this->Compare(array[i],element))
        {
            RemoveByindex(i);
            i--;
        }
    }
 }

 ElementType *DynamicArray::FindByIndex(size_t index)//O(1)
 {
    if(index>=size)
    {
        return nullptr;
    }
    return &array[index];
 }

 DynamicArray DynamicArray::FindByElement(const ElementType &element)//O(n)
 {
    DynamicArray result;
    for(size_t i=0;i<size;i++)
    {
        if(this->Compare(array[i],element))
        {
                result.Inserttail((void*)i);
        }
    }
    return result;
 }

 void DynamicArray::UpdateByIndex(size_t index, const ElementType &newValue)//O(1)
 {
    if(index>=size)
    {
        std::cout<<"位置不合法"<<std::endl;
    }
    array[index]=newValue;
 }

 void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)//O(n)
 {
    for(size_t i=0;i<size;i++)
    {
        if(this->Compare(array[i],oldValue))
        {
            array[i]=newValue;
        }
    }
 }

 ElementType &DynamicArray::operator[](int index)
 {
     return array[index];
 }

 void DynamicArray::Sort()
 {
    FastSort(0,size-1,0,2*log2(size));//最大递归深度为什么是2*log2（size）：理想状态下每次选的tmp在最中间，所以一共进行n/2/2/2...次递归 直到排到最后，
    //列出表达式为2^x=n,一共进行了x=log2n， 最大排列次数：每个数都要排（倒叙排列），一共进行了n次排列，所以取中间值2*log2n 
 }

 void DynamicArray::Duplicate()//o(n)
 {
    for(size_t i=1;i<size;i++)
    {
        if(this->Compare(array[i],array[i-1]))
        {
            RemoveByindex(i);
            i--;
        }
    }
 }

 DynamicArray DynamicArray::Merge(const DynamicArray &a)
 {
    DynamicArray result;
    size_t first=0;//当前数组
    size_t second=0;//传进来的数组
    while(first<this->size&&second<a.size)
    {
        if(this->ComBig(a.array[second],array[first]))
            result.Inserttail(array[first++]);
        else    
            result.Inserttail(a.array[second++]);

    }
    while(first<this->size)
        result.Inserttail(array[first++]);
    while(second<a.size)
        result.Inserttail(a.array[second++]);
    return result;
   
 }

 DynamicArray DynamicArray::FdInSctn(const DynamicArray& a)
 {
    DynamicArray result;
    size_t first=0;//当前数组
    size_t second=0;//传进来的数组
    while(first<this->size&&second<a.size)
    {
        if(this->Compare(array[first],a.array[second]) )
        {
            result.Inserttail(array[first++]);
            second++;
        }
        else if(this->ComBig(a.array[second],array[first]))
        {
            first++;
        }
        else if(this->ComBig(array[first],a.array[second]))
        {
            second++;
        }
    }
  
    return result;

     
 }

 DynamicArray DynamicArray::FindUnionset(const DynamicArray &a)//O(n)
 {
    DynamicArray result;
    size_t first=0;//当前数组
    size_t second=0;//传进来的数组
    while(first<this->size&&second<a.size)
    {
        if(this->Compare(array[first],a.array[second]))
        {
            result.Inserttail(array[first++]);
            second++;
        }
        else if(this->ComBig(a.array[second],array[first]))
        {
            result.Inserttail(array[first++]);
        }
        else if(this->ComBig(array[first],a.array[second]))
        {
            result.Inserttail(a.array[second++]);
        }
    }
    while(first<this->size)
        result.Inserttail(array[first++]);
    while(second<a.size)
        result.Inserttail(a.array[second++]);
    return result;
 }

 DynamicArray DynamicArray::FindDifference(const DynamicArray &a)
 {
    DynamicArray result;
    size_t first=0;
    size_t second=0;
      while(first<this->size&&second<a.size)
    {
        if(this->Compare(array[first],a.array[second]))
        {
                first++;
                second++;
        }
        else if(this->ComBig(a.array[second],array[first]))
        {
            result.Inserttail(array[first++]);
        }
        else if(this->ComBig(array[first],a.array[second]))
        {
            result.Inserttail(a.array[second++]);
        }
    }
    while(first<this->size)
        result.Inserttail(array[first++]);
    while(second<a.size)
        result.Inserttail(a.array[second++]);
   
    return result;


 }


 bool DynamicArray::operator==(const DynamicArray &a)//O(n)
 {
     if(this->size!=a.size)
     {
       return false;

     }
    size_t first=0;
    size_t second=0;
   while(first<this->size&&second<a.size)
    {
            if(this->ComBig((array[first++]),a.array[second++])||this->ComBig(a.array[second++],(array[first++])))
                return false;
    }
    return true;
 }

 size_t DynamicArray::BinarySearch(const ElementType &element)
 {
    size_t left=0;
    size_t right=size-1;
    while(left<=right)
    {
        size_t mid=left+(right-left)/2;
        if(this->Compare(array[mid],element))
        {
            return mid;
        }
        else if(this->ComBig(array[mid],element) )
        {   
            //size_t不能取符号负值，所以当mid=0，返回上限值
            if(mid==0)
                return ULONG_MAX;
            right=mid-1;
        }
        else if(this->ComBig(element,array[mid]))
        {
            left=mid+1;
        }
    }
    return ULONG_MAX;
 }

 bool DynamicArray::Contains(const DynamicArray &a)
 {
    //交集是自己本身
    //  DynamicArray s=FdInSctn(a);//O（2n）
    //  return s==a;
    size_t j=0; //O(n)
    for(size_t i=0;i<size;i++)
    {
        if(this->Compare(array[i],a.array[j]))
            j++;
    }
    return j==a.size;
   


 }

 DynamicArray DynamicArray::SubSquence(size_t index, size_t len)
 {
    DynamicArray result;
    if(index+len>size)
        return result;
    for(size_t i=0;i<len;i++)
    {
        result.Inserttail(array[index+i]);
    }
    return result;
 }

 bool DynamicArray::ContinsContains(const DynamicArray &a)
 {
    for(size_t i=0;i<=size-a.size;i++)//滑动窗口
    {
        if(SubSquence(i,a.size)==a)
        {
            return true;
        }
    }
    return false;     
 }

 size_t DynamicArray::partition(size_t start,size_t end)
 {
    size_t left=start;
    size_t right=end;
    ElementType temp=array[start];
    while(left<right)
    {
        while(this->ComBig(array[right],temp) &&left<right)
            right--;
        if(left<right)
            array[left++]=array[right];
        while(this->ComBig(temp,array[left])&&left<right)
            left++;
        if(left<right)
            array[right--]=array[left];
    }
    array[left]=temp;
    return left;
 }

 // 爆栈：递归深度过深导致栈空间不足的情况
 void DynamicArray::FastSort(size_t start, size_t end,size_t CurDepth,size_t MaxDepth)
 {
    if(start>=end)
        return;
    //如果没有达到最大递归深度
    if(CurDepth<MaxDepth)
    {
        size_t par=partition(start,end);//对数列分组
        if(par!=0)//当par=0，par-1非常大(size_t是无符号长整型)
             FastSort(start,par-1,CurDepth+1,MaxDepth);
        FastSort(par+1,end,CurDepth+1,MaxDepth);
    }
    //超过最大深度，改用插入排序
    else
    {
        InsertSort(start,end);
    }
    
    

 }

 void DynamicArray::InsertSort(size_t start, size_t end)
 {
    for(size_t i=start+1;i<=end;i++)
    {
        size_t j=i;
        ElementType tmp=array[i];
        for(;j>start;j--)
        {
            if(this->ComBig(array[j-1],tmp) )
                array[j]=array[j-1];
            else    
                break;
        }
        array[j]=tmp;
    }
 }

 void DynamicArray::ReSize(size_t capacity)
 {
    this->capacity=capacity;
    this->size=size>capacity?capacity:size;
    ElementType *newPtr=new ElementType[capacity];
    for(size_t i=0;i<size;i++)
    {
        newPtr[i]=array[i];
    }
    delete []array;
    array=newPtr;
 }

void DynamicArray::show()
{
    for(size_t i=0;i<size;i++)
    {
        Print(array[i]);
    }
    std::cout<<std::endl;

}